package main.java.LeetCode.ClassicalAlgorithm.Tree.Impl;

import main.java.LeetCode.CommonSolution.TriesNode;

import java.util.*;

@SuppressWarnings("ALL")
public class Tries {

    private final TriesNode root = new TriesNode();

    public void insert(String words){

        if(select(words)){
            System.out.println("["+words+"]"+" is already existed");
            return;
        }

        TriesNode temp = root;
        for(int i = 0;i<words.length();i++){
            char key = words.charAt(i);

            if(!temp.isContainsKey(key)){
                temp.initKeys(key);
            }
            if(i==words.length()-1)
                temp.setKeyEnd(key,true);

            temp.setKeyCounte(key,1);
            temp = temp.getKeyNode(key);
        }
    }

    public boolean select(String words){
        TriesNode temp = root;
        for(int i = 0;i<words.length();i++){
            char key = words.charAt(i);

            if(!temp.isContainsKey(key)||temp.getKeyCount(key)<=0||(i==words.length()-1&&!temp.getKeyEnd(key)))
                return false;
            temp = temp.getKeyNode(key);
        }
        return true;
    }

    public boolean delete(String words){
        if(!select(words)){
            System.out.println("["+words+"]"+" is not exist!");
            return false;
        }

        TriesNode temp = root;

        for (int i = 0; i < words.length(); i++) {
            char key = words.charAt(i);
            temp.setKeyCounte(key,-1);
            if(i==words.length()-1)
                temp.setKeyEnd(key,false);

            temp = temp.getKeyNode(key);
        }


        return true;
    }

    public boolean update(String words,String changes){
        if(!delete(words))
            return false;
        insert(changes);
        return true;
    }

    public List<String> selectByPrefix(String s){
        if(s.length()==0)
            return showAll();
        TriesNode temp = root;
        List<String> list = new LinkedList<>();
        for(int i = 0;i<s.length();i++){
            char key = s.charAt(i);

            if(!temp.isContainsKey(key)||temp.getKeyCount(key)<=0){
                return null;
            }

            if(i==s.length()-1&&temp.getKeyEnd(key))
                list.add(s);
            temp = temp.getKeyNode(key);
        }

        doShowAll(temp,list,s);

        return list;
    }

    public List<String> showAll(){
        List<String> list = new LinkedList<>();
        doShowAll(root,list,"");
        return list;
    }
    private void doShowAll(TriesNode root,List<String> list,String s){
        Set<Character> allKey = root.getAllKey();

        for(char key:allKey){

            if(root.getKeyCount(key)<=0)
                continue;

            if(root.getKeyEnd(key)){
                list.add(s+key);
            }

            doShowAll(root.getKeyNode(key),list,s+key);
        }
    }
}
